Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Sorting Algorithms

In this lesson, we’ll explore four different sorting algorithms:

  • Bubble Sort
  • Merge Sort
  • Quick Sort
  • Counting Sort.

We’ll provide code for each algorithm, followed by a detailed complexity analysis. Each algorithm will be evaluated based on its time and space complexity, helping you understand when to use each one.

1. Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Java
Saved to Cloud

. . . .

Time Complexity for Bubble Sort

  • Outer loop: The outer loop runs N times, where N is the length of the input array. This contributes a time complexity of for the outer loop.
  • Inner loop (nested): For each iteration of the outer loop, the inner loop runs N - i - 1 times. In the first iteration, the inner loop runs approximately N - 1 times, in the second iteration N - 2 times, and so on. The total number of comparisons made can be expressed as:

This simplifies to .

Overall time complexity: . The nested loops dominate the runtime, resulting in quadratic time complexity.

Space Complexity for Bubble Sort

  • The algorithm only uses a few variables (i, j, and temporary variables for swapping), which require constant space.
  • No additional data structures are used that depend on the input size.

Overall space complexity: . Bubble Sort is an in-place sorting algorithm, so it only requires a constant amount of extra space.

2. Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and then merges them back together in sorted order.

Java
Saved to Cloud

. . . .

Time Complexity for Merge Sort

  1. Divide Step:

    • The mergeSort function splits the array into two halves.
    • Time Complexity for Division: for calculating mid and slicing arrays.
    • This division step is performed at each recursive level, with each level having approximately divisions for an input of size .
  2. Recursive Calls:

    • The function recursively calls mergeSort on both the left and right halves.
    • Number of Levels: The array is divided until each subarray has one element, resulting in approximately levels of recursion.
  3. Merge Step:

    • The merging process iterates over both halves and sorts them.
    • Time Complexity for Merging: at each level since all elements are processed once during merging.
    • Each level processes the entire array of size N.

Overall Time Complexity:

  • The merging process runs at each level, and there are levels of recursion:

Space Complexity for Merge Sort

  1. Auxiliary Space for Left and Right Halves:

    • At each level of recursion, space is used for creating the left and right subarrays (arr[:mid] and arr[mid:]).
    • This leads to additional space for splitting arrays at each level of recursion.
  2. Recursive Call Stack:

    • The depth of the recursion stack is due to the binary splitting.
    • Each call adds a frame to the stack, but these do not contribute to more than space.

Overall Space Complexity:

  • The merge process and auxiliary space for storing left and right halves contribute to .
  • The recursive stack contributes space.

Total Space Complexity:

3. Quick Sort

Quick Sort is a highly efficient sorting algorithm that picks a pivot and partitions the array into subarrays, sorting them recursively.

Java

. . . .

Time Complexity for Quick Sort

  1. Partition Step:

    • The array is partitioned into left, middle, and right subarrays based on the pivot.
    • Time Complexity for Partitioning: for each call as it requires iterating through the array to build the subarrays left, middle, and right.
  2. Recursive Calls:

    • The quickSort function is recursively called on left and right subarrays.
    • Best and Average Case:
      • If the pivot splits the array into two roughly equal parts, each call processes elements, leading to levels of recursion.
      • Total Time Complexity: .
    • Worst Case:
      • If the pivot is the smallest or largest element (e.g., already sorted or reverse-sorted arrays), one partition will have elements, leading to levels of recursion.
      • Total Time Complexity in Worst Case: .

Overall Time Complexity:

  • Best and Average Case: .
  • Worst Case: .

Space Complexity for Quick Sort

  1. Auxiliary Space:

    • The partitioning step creates new subarrays (left, middle, right) at each level, requiring additional space proportional to for each partition.
  2. Recursive Call Stack:

    • The depth of the recursion stack is in the best and average cases, but can be in the worst case for highly unbalanced splits.

Overall Space Complexity:

  • Best and Average Case: for the recursion stack.
  • Worst Case: due to the maximum recursion depth.

Total Space Complexity:

  • Auxiliary Space: for subarrays created at each level.

4. Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each element and uses this count to place them in the correct position.

Java

. . . .

Time Complexity for Counting Sort

  1. Finding the Maximum Element (max(arr)):

    • Time Complexity: – This step iterates through the array once to find the maximum value.
  2. Creating the Count Array:

    • Time Complexity: , where is the value of the maximum element in the array. This step initializes an array of size K + 1 to zero.
  3. Counting the Occurrences:

    • The for loop that iterates through arr and increments the count in the count array runs in:
      • Time Complexity: – It iterates through each element in the input array once.
  4. Building the Sorted Array:

    • The second for loop iterates over the count array and extends sorted_arr based on the counts.
    • Time Complexity: – The loop runs times, and extending sorted_arr takes across all iterations.

Overall Time Complexity:

  • The total time complexity is:

    This makes Counting Sort efficient when (the range of input values) is not significantly larger than .

Space Complexity for Counting Sort

  1. Count Array:

    • The count array is created with a size of , where is the maximum element in arr.
    • Space Complexity: – This space depends on the range of input values.
  2. Sorted Array:

    • The sorted_arr is created to store the sorted output.
    • Space Complexity: – It stores the sorted elements of the input array.

Overall Space Complexity:

  • The total space complexity is:

Which Sorting Algorithm is Better?

  • Bubble Sort: Simple to implement but inefficient for large datasets ().
  • Merge Sort: Reliable performance but uses space.
  • Quick Sort: Efficient for most cases with time, but worst case is . Uses less space ().
  • Counting Sort: Ideal for small ranges of integers; time but uses more space ().

Best Overall Choice: Quick Sort for general cases due to its efficiency and average time. Merge Sort is a close second for guaranteed performance, especially when space is not a concern.

Quiz
Graph Algorithms
Mark as Completed

On this page

  1. Bubble Sort

Time Complexity for Bubble Sort

Space Complexity for Bubble Sort

  1. Merge Sort

Time Complexity for Merge Sort

Space Complexity for Merge Sort

  1. Quick Sort

Time Complexity for Quick Sort

Space Complexity for Quick Sort

  1. Counting Sort

Time Complexity for Counting Sort

Space Complexity for Counting Sort

Which Sorting Algorithm is Better?